Termination w.r.t. Q proof of TRS/SK904.21.trs

Termination w.r.t. Q of the following Term Rewriting System could be proven:

Q restricted rewrite system:
The TRS R consists of the following rules:

and₂(x, or₂(y, z)) -> or₂(and₂(x, y), and₂(x, z))
and₂(x, and₂(y, y)) -> and₂(x, y)
or₂(or₂(x, y), and₂(y, z)) -> or₂(x, y)
or₂(x, and₂(x, y)) -> x
or₂(true, y) -> true
or₂(x, false) -> x
or₂(x, x) -> x
or₂(x, or₂(y, y)) -> or₂(x, y)
and₂(x, true) -> x
and₂(false, y) -> false
and₂(x, x) -> x

Q is empty.

↳ QTRS

  ↳ DependencyPairsProof

Q restricted rewrite system:
The TRS R consists of the following rules:

and₂(x, or₂(y, z)) -> or₂(and₂(x, y), and₂(x, z))
and₂(x, and₂(y, y)) -> and₂(x, y)
or₂(or₂(x, y), and₂(y, z)) -> or₂(x, y)
or₂(x, and₂(x, y)) -> x
or₂(true, y) -> true
or₂(x, false) -> x
or₂(x, x) -> x
or₂(x, or₂(y, y)) -> or₂(x, y)
and₂(x, true) -> x
and₂(false, y) -> false
and₂(x, x) -> x

Q is empty.

Using Dependency Pairs [1,13] we result in the following initial DP problem:
Q DP problem:
The TRS P consists of the following rules:

AND₂(x, or₂(y, z)) -> OR₂(and₂(x, y), and₂(x, z))
AND₂(x, or₂(y, z)) -> AND₂(x, z)
AND₂(x, or₂(y, z)) -> AND₂(x, y)
OR₂(x, or₂(y, y)) -> OR₂(x, y)
AND₂(x, and₂(y, y)) -> AND₂(x, y)

The TRS R consists of the following rules:

and₂(x, or₂(y, z)) -> or₂(and₂(x, y), and₂(x, z))
and₂(x, and₂(y, y)) -> and₂(x, y)
or₂(or₂(x, y), and₂(y, z)) -> or₂(x, y)
or₂(x, and₂(x, y)) -> x
or₂(true, y) -> true
or₂(x, false) -> x
or₂(x, x) -> x
or₂(x, or₂(y, y)) -> or₂(x, y)
and₂(x, true) -> x
and₂(false, y) -> false
and₂(x, x) -> x

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ DependencyGraphProof

Q DP problem:
The TRS P consists of the following rules:

AND₂(x, or₂(y, z)) -> OR₂(and₂(x, y), and₂(x, z))
AND₂(x, or₂(y, z)) -> AND₂(x, z)
AND₂(x, or₂(y, z)) -> AND₂(x, y)
OR₂(x, or₂(y, y)) -> OR₂(x, y)
AND₂(x, and₂(y, y)) -> AND₂(x, y)

The TRS R consists of the following rules:

and₂(x, or₂(y, z)) -> or₂(and₂(x, y), and₂(x, z))
and₂(x, and₂(y, y)) -> and₂(x, y)
or₂(or₂(x, y), and₂(y, z)) -> or₂(x, y)
or₂(x, and₂(x, y)) -> x
or₂(true, y) -> true
or₂(x, false) -> x
or₂(x, x) -> x
or₂(x, or₂(y, y)) -> or₂(x, y)
and₂(x, true) -> x
and₂(false, y) -> false
and₂(x, x) -> x

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph [13,14,18] contains 2 SCCs with 1 less node.

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ DependencyGraphProof

        ↳ AND

          ↳ QDP

            ↳ QDPOrderProof

          ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

OR₂(x, or₂(y, y)) -> OR₂(x, y)

The TRS R consists of the following rules:

and₂(x, or₂(y, z)) -> or₂(and₂(x, y), and₂(x, z))
and₂(x, and₂(y, y)) -> and₂(x, y)
or₂(or₂(x, y), and₂(y, z)) -> or₂(x, y)
or₂(x, and₂(x, y)) -> x
or₂(true, y) -> true
or₂(x, false) -> x
or₂(x, x) -> x
or₂(x, or₂(y, y)) -> or₂(x, y)
and₂(x, true) -> x
and₂(false, y) -> false
and₂(x, x) -> x

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [13].

The following pairs can be oriented strictly and are deleted.

OR₂(x, or₂(y, y)) -> OR₂(x, y)

The remaining pairs can at least be oriented weakly.
none
Used ordering: Polynomial Order [17,21] with Interpretation:

POL( OR₂(x₁, x₂) ) = x₂

POL( or₂(x₁, x₂) ) = x₂ + 1

The following usable rules [14] were oriented: none

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ DependencyGraphProof

        ↳ AND

          ↳ QDP

            ↳ QDPOrderProof

              ↳ QDP

                ↳ PisEmptyProof

          ↳ QDP

Q DP problem:
P is empty.
The TRS R consists of the following rules:

and₂(x, or₂(y, z)) -> or₂(and₂(x, y), and₂(x, z))
and₂(x, and₂(y, y)) -> and₂(x, y)
or₂(or₂(x, y), and₂(y, z)) -> or₂(x, y)
or₂(x, and₂(x, y)) -> x
or₂(true, y) -> true
or₂(x, false) -> x
or₂(x, x) -> x
or₂(x, or₂(y, y)) -> or₂(x, y)
and₂(x, true) -> x
and₂(false, y) -> false
and₂(x, x) -> x

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The TRS P is empty. Hence, there is no (P,Q,R) chain.

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ DependencyGraphProof

        ↳ AND

          ↳ QDP

          ↳ QDP

            ↳ QDPOrderProof

Q DP problem:
The TRS P consists of the following rules:

AND₂(x, or₂(y, z)) -> AND₂(x, z)
AND₂(x, or₂(y, z)) -> AND₂(x, y)
AND₂(x, and₂(y, y)) -> AND₂(x, y)

The TRS R consists of the following rules:

and₂(x, or₂(y, z)) -> or₂(and₂(x, y), and₂(x, z))
and₂(x, and₂(y, y)) -> and₂(x, y)
or₂(or₂(x, y), and₂(y, z)) -> or₂(x, y)
or₂(x, and₂(x, y)) -> x
or₂(true, y) -> true
or₂(x, false) -> x
or₂(x, x) -> x
or₂(x, or₂(y, y)) -> or₂(x, y)
and₂(x, true) -> x
and₂(false, y) -> false
and₂(x, x) -> x

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [13].

The following pairs can be oriented strictly and are deleted.

AND₂(x, or₂(y, z)) -> AND₂(x, z)
AND₂(x, or₂(y, z)) -> AND₂(x, y)

The remaining pairs can at least be oriented weakly.

AND₂(x, and₂(y, y)) -> AND₂(x, y)

Used ordering: Polynomial Order [17,21] with Interpretation:

POL( AND₂(x₁, x₂) ) = x₂

POL( or₂(x₁, x₂) ) = x₁ + x₂ + 1

POL( and₂(x₁, x₂) ) = x₂

The following usable rules [14] were oriented: none

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ DependencyGraphProof

        ↳ AND

          ↳ QDP

          ↳ QDP

            ↳ QDPOrderProof

              ↳ QDP

                ↳ QDPOrderProof

Q DP problem:
The TRS P consists of the following rules:

AND₂(x, and₂(y, y)) -> AND₂(x, y)

The TRS R consists of the following rules:

and₂(x, or₂(y, z)) -> or₂(and₂(x, y), and₂(x, z))
and₂(x, and₂(y, y)) -> and₂(x, y)
or₂(or₂(x, y), and₂(y, z)) -> or₂(x, y)
or₂(x, and₂(x, y)) -> x
or₂(true, y) -> true
or₂(x, false) -> x
or₂(x, x) -> x
or₂(x, or₂(y, y)) -> or₂(x, y)
and₂(x, true) -> x
and₂(false, y) -> false
and₂(x, x) -> x

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [13].

The following pairs can be oriented strictly and are deleted.

AND₂(x, and₂(y, y)) -> AND₂(x, y)

The remaining pairs can at least be oriented weakly.
none
Used ordering: Polynomial Order [17,21] with Interpretation:

POL( AND₂(x₁, x₂) ) = x₂

POL( and₂(x₁, x₂) ) = x₂ + 1

The following usable rules [14] were oriented: none

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ DependencyGraphProof

        ↳ AND

          ↳ QDP

          ↳ QDP

            ↳ QDPOrderProof

              ↳ QDP

                ↳ QDPOrderProof

                  ↳ QDP

                    ↳ PisEmptyProof

Q DP problem:
P is empty.
The TRS R consists of the following rules:

and₂(x, or₂(y, z)) -> or₂(and₂(x, y), and₂(x, z))
and₂(x, and₂(y, y)) -> and₂(x, y)
or₂(or₂(x, y), and₂(y, z)) -> or₂(x, y)
or₂(x, and₂(x, y)) -> x
or₂(true, y) -> true
or₂(x, false) -> x
or₂(x, x) -> x
or₂(x, or₂(y, y)) -> or₂(x, y)
and₂(x, true) -> x
and₂(false, y) -> false
and₂(x, x) -> x

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The TRS P is empty. Hence, there is no (P,Q,R) chain.